class Solution {
public:
    //f[i][j]表示考虑前i个物品，并且总体积不低于于j的最小值
    const int INF = 0x3f;
    static const int N = 3000;
    int dp[N];
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for(auto e: stones) sum += e;
        int target = sum / 2;
        memset(dp, INF, sizeof dp);
        dp[0] = 0;

        for(int i = 1; i <= stones.size(); ++i)
            for(int j = target; j > 0; --j)
            {
                int need = max(0, j - stones[i - 1]);
                if(dp[need] != 0x3f3f3f3f) 
                    dp[j] = min(dp[j], dp[need] + stones[i - 1]);
            }
            // print(stones.size(), target);
            // cout << dp[stones.size()][target] << ' ' << sum << endl;
            return abs(2 * dp[target] - sum);
    }
};